Thực đơn
Mã hóa Huffman Dẫn nhậpĐể mã hóa các ký hiệu (ký tự, chữ số,...) ta thay chúng bằng các xâu nhị phân, được gọi là từ mã của ký hiệu đó. Chẳng hạn bộ mã ASCII, mã hóa cho 256 ký hiệu là biểu diễn nhị phân của các số từ 0 đến 255, mỗi từ mã gồm 8 bít. Trong ASCII từ mã của ký tự "a" là 1100001, của ký tự "A" là 1000001. Trong cách mã hóa này các từ mã của tất cả 256 ký hiệu có độ dài bằng nhau (mỗi từ mã 8 bít). Nó được gọi là mã hóa với độ dài không đổi.
Khi mã hóa một tài liệu có thể không sử dụng đến tất cả 256 ký hiệu. Hơn nữa trong tài liệu chữ cái "a" chỉ có thể xuất hiện 1000000 lần còn chữ cái "A" có thể chỉ xuất hiện 2, 3 lần. Như vậy ta có thể không cần dùng đủ 8 bít để mã hóa cho một ký hiệu, hơn nữa độ dài (số bít) dành cho mỗi ký hiệu có thể khác nhau, ký hiệu nào xuất hiện nhiều lần thì nên dùng số bít ít, ký hiệu nào xuất hiện ít thì có thể mã hóa bằng từ mã dài hơn. Như vậy ta có việc mã hóa với độ dài thay đổi. Tuy nhiên, nếu mã hóa với độ dài thay đổi, khi giải mã ta làm thế nào phân biệt được xâu bít nào là mã hóa của ký hiệu nào. Một trong các giải pháp là dùng các dấu phẩy (",") hoặc một ký hiệu quy ước nào đó để tách từ mã của các ký tự đứng cạnh nhau. Nhưng như thế số các dấu phẩy sẽ chiếm một không gian đáng kể trong bảng mã. Một cách giải quyết khác dẫn đến khái niệm mã tiền tố
Đương nhiên mã hóa với độ dài không đổi là mã tiền tố.
Ví dụ: Giả sử mã hóa từ "ARRAY", tập các ký hiệu cần mã hóa gồm 3 chữ cái "A","R","Y".* 0/ \1 A * 0/ \1 R Y
Từ ví dụ trên thấy mã hóa của xâu "ARRAY" bằng mã độ dài cố định mất 10 bít, bằng mã tiền tố đã đưa ra mất 8 bít, tiết kiệm được 20%. Bài toán đặt ra là bộ mã tiền tố đã tối ưu chưa.
Thực đơn
Mã hóa Huffman Dẫn nhậpLiên quan
Mã Mã di truyền Mã Siêu Mã số điện thoại quốc tế Mãn Châu Quốc Mã Morse Mã Gia Kỳ Mã vạch Mãn Châu Mã hóa video hiệu quả caoTài liệu tham khảo
WikiPedia: Mã hóa Huffman http://www.cs.sfu.ca/cs/CC/365/li/squeeze http://wiki.cc/php/?title=Huffman http://www.research.att.com/projects/OEIS?Anum=A09... http://alexvn.freeservers.com/s1/huffman_template_... http://www.huffmancoding.com/david/algorithm.html http://www.huffmancoding.com/david/scientific.html http://www.informatik.uni-trier.de/~ley/db/conf/st... http://www.cs.duke.edu/csed/poop/huff/info/ http://web-cat.cs.vt.edu/AlgovizWiki/HuffmanCoding... http://semillon.wpi.edu/~aofa/AofA/msg00040.html